import java.util.Arrays;

public class Dijkstra {
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        // 邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;// 表示不可连接
        matrix[0] = new int[] { N, 5, 7, N, N, N, 2 };
        matrix[1] = new int[] { 5, N, N, 9, N, N, 3 };
        matrix[2] = new int[] { 7, N, N, N, 8, N, N };
        matrix[3] = new int[] { N, 9, N, N, N, 4, N };
        matrix[4] = new int[] { N, N, 8, N, N, 5, 4 };
        matrix[5] = new int[] { N, N, N, 4, 5, N, 6 };
        matrix[6] = new int[] { 2, 3, N, N, 4, 6, N };
        Mgraph mgraph = new Mgraph(vertex,matrix);
        mgraph.print();
        mgraph.dijkstra(6);
        mgraph.show();
    }
}
class Mgraph{
    public char[] vertex;
    public int[][] matrix;
    public VisitedVertex visitedVertex;

    public Mgraph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }
    public void print(){
        for (int[] m:matrix) {
            System.out.println(Arrays.toString(m));
        }
    }
    public void dijkstra(int index){
         visitedVertex=new VisitedVertex(vertex.length,index);
         update(index);

        for (int i = 0; i < vertex.length; i++) {
            index=visitedVertex.UpdateArr();
            update(index);
        }
    }
    public void show(){
        visitedVertex.show();
    }

    public void update(int index){
        int len=0;
        for (int i = 0; i < matrix[index].length-1; i++) {
            len= visitedVertex.getDis(index)+matrix[index][i];
            if (!visitedVertex.isArr(i)&&len< visitedVertex.getDis(i)){
                visitedVertex.Updatepre(i,index);//跟新i的前驱节点为index
                visitedVertex.UpdateDis(i,len);//更新开头到i距离为len
            }
        }
    }

}

/**
 * already_arr;// 记录各个顶点是否为访问过
 * pre_visited;// 记录本下标顶点所对应的前一个顶点的下标
 * dis;// 记录出发顶点到与其相连的所有顶点的距离，将距离最短的放入dis中
 */
class VisitedVertex{
    public int[] already_arr;
    public int[] pre_visited;
    public int[] Dis;

    public VisitedVertex(int length,int index) {
        already_arr = new int[length];
        this.pre_visited = new int[length];
        Dis = new int[length];

        Arrays.fill(Dis,65535);
        Dis[index]=0;
        already_arr[index]=1;
    }

    public void Updatepre(int index,int i){
        pre_visited[index]=i;
    }

    public void Updatearr(int index){
        already_arr[index]=1;
    }

    public void UpdateDis(int index,int len){
        Dis[index]=len;
    }

    public boolean isArr(int index){//判断有没有被访问过
        return already_arr[index]==1;
    }

    public int getDis(int index){//返回开始到index的最短距离
        return Dis[index];
    }


    public int UpdateArr(){
        int min=65535,index=0;
        for (int i = 0; i < already_arr.length; i++) {
            if (!isArr(i)&&min>getDis(i)){
                min=Dis[i];
                index=i;
            }
        }
        Updatearr(index);
        return index;
    }
    public void show(){
        for (int arr:already_arr) {
            System.out.print(arr+" ");
        }
        System.out.println();
        for (int dis:Dis) {
            System.out.print(dis+" ");
        }
        System.out.println();
        for (int pre:pre_visited) {
            System.out.print(pre+" ");
        }
    }


}
